﻿using System;
using System.Collections.Generic;
using System.Threading.Tasks;

namespace SGEngine.ProfilerEx
{
    [Serializable]
    public class ProfilerTreeNode 
    {
        // 创建一个对象用于锁定
        private static object m_LockObject = new object();
        private static readonly Queue<ProfilerTreeNode> s_CachedNodes = new Queue<ProfilerTreeNode>(1024);
        private static int s_FrameCount = 0;
        
        public static ProfilerTreeNode RequestNode(string name, int depth, long gc, long selfGc, double timeMs, double selfMs, int callCount = 1, bool isLeaf = false)
        {
            ProfilerTreeNode node = null;
            lock (m_LockObject)
            {
                node = s_CachedNodes.Count > 0 ? s_CachedNodes.Dequeue() : new ProfilerTreeNode();
            }
            node.Name = name;
            node.Depth = depth;
            node.Gc = gc;
            node.SelfGc = selfGc;
            node.TimeMs = timeMs;
            node.SelfMs = selfMs;
            node.CallCount = callCount;
            node.IsLeaf = isLeaf;
            return node;
        }

        public static void ReleaseNode(ProfilerTreeNode node)
        {
            foreach (var child in node.Children)
            {
                ReleaseNode(child);
            }
            node.Name = "";
            node.Depth = 0;
            node.Gc = 0;
            node.TimeMs = 0;
            node.SelfMs = 0;
            node.CallCount = 0;
            node.Children.Clear();
            node.SelfGc = -1;
            node.Parent = null;
            lock (m_LockObject)
            {
                s_CachedNodes.Enqueue(node);
            }
        }

        public static ProfilerTreeNode DeepCopy(ProfilerTreeNode srcNode)
        {
            var targetNode = ProfilerTreeNode.RequestNode(srcNode.Name, srcNode.Depth, srcNode.Gc, srcNode.SelfGc, srcNode.TimeMs,
                srcNode.SelfMs, srcNode.CallCount);
            foreach (var srcChild in srcNode.Children)
            {
                var targetChild = DeepCopy(srcChild);
                targetNode.AddChild(targetChild);
            }
            return targetNode;
        }

        public string Name;
        public long Gc;

        public string GcDesc => UnitConvertUtility.GetPrettySizeDesc(Gc);
        /// <summary>
        /// 调用次数
        /// </summary>
        public int CallCount;
        public double TimeMs;
        public string TimeMsDesc => UnitConvertUtility.GetPrettyTimeMsDesc(TimeMs);
        public double SelfMs;
        public string SelfMsDesc => UnitConvertUtility.GetPrettyTimeMsDesc(SelfMs);
        public int Depth;
        public readonly List<ProfilerTreeNode> Children = new List<ProfilerTreeNode>();
        public ProfilerTreeNode Parent;
        /// <summary>
        /// 是否叶子节点（终端节点）
        /// </summary>
        public bool IsLeaf;
        public long SelfGc = 0;

        public string AvgSelfMsgDesc => UnitConvertUtility.GetPrettyTimeMsDesc(SelfMs/CallCount);
        public string AvgFrameSelfMsgDesc => UnitConvertUtility.GetPrettyTimeMsDesc(SelfMs/ProfilerExData.Instance.frameCount);
        public string AvgTimeMsDesc => UnitConvertUtility.GetPrettyTimeMsDesc(TimeMs/CallCount);
        public string AvgFrameTimeMsDesc => UnitConvertUtility.GetPrettyTimeMsDesc(TimeMs/ProfilerExData.Instance.frameCount);

        public string SelfGcDesc => UnitConvertUtility.GetPrettySizeDesc(SelfGc);

        private ProfilerTreeNode()
        {
        }

        public void CalSelfGc()
        {
            foreach (var child in Children)
            {
                if (child.Name.Equals("GC.Alloc"))
                {
                    SelfGc = child.Gc;
                    break;
                }
            }
        }

        public void SortChildren(string columnName, bool ascending)
        {
            Children.MergeSort((node1, node2) =>
            {
                // if (ascending)
                // {
                //     switch (columnName)
                //     {
                //         case "name":
                //         {
                //             return String.Compare(node1.Name, node2.Name, StringComparison.OrdinalIgnoreCase);
                //         }
                //         case "gc":
                //         {
                //             return node1.Gc.CompareTo(node2.Gc);
                //         }
                //         case "callcount":
                //         {
                //             return node1.CallCount.CompareTo(node2.CallCount);
                //         }
                //         case "timems":
                //         {
                //             return node1.TimeMs.CompareTo(node2.TimeMs);
                //         }
                //         case "selfms":
                //         {
                //             return node1.SelfMs.CompareTo(node2.SelfMs);
                //         }
                //     }
                // }
                // else
                {
                    switch (columnName)
                    {
                        case "name":
                        {
                            return String.Compare(node2.Name, node1.Name, StringComparison.OrdinalIgnoreCase);
                        }
                        case "gc":
                        {
                            return node2.Gc.CompareTo(node1.Gc);
                        }
                        case "selfgc":
                        {
                            return node2.SelfGc.CompareTo(node1.SelfGc);
                        }
                        case "callcount":
                        {
                            return node2.CallCount.CompareTo(node1.CallCount);
                        }
                        case "timems":
                        case "avgframetimems":
                        {
                            return node2.TimeMs.CompareTo(node1.TimeMs);
                        }
                        case "selfms":
                        case "avgframeselfms":
                        {
                            return node2.SelfMs.CompareTo(node1.SelfMs);
                        }
                    }
                }
                
                return node2.Gc.CompareTo(node1.Gc);
                
            });
            foreach (var node in Children)
            {
                node.SortChildren(columnName, ascending);
            }
        }

        public void AddChild(ProfilerTreeNode child)
        {
            Children.Add(child);
            child.Parent = this;
        }

        public override string ToString()
        {
            var tab = Depth >= 0 ? new string('\t', Depth) : "..";
            return $"{tab}n:{Name} v:{Gc} c:{Children.Count}";
        }
    }
    public class ProfilerTreeData: IDisposable
    {
        public const int k_DepthSepNum = 10000;
        public ProfilerTreeNode Root;
        public ProfilerTreeData(ProfilerTreeNode root)
        {
            Root = root;
        }

        public void MakeSelfGc()
        {
            MakeSelfGc(Root);
        }

        private void MakeSelfGc(ProfilerTreeNode node)
        {
            node.CalSelfGc();
            foreach (var child in node.Children)
            {
                MakeSelfGc(child);
            }
        }
        
        public override string ToString()
        {
            var depthsList = ConvertTreeToDepthsList(this);
            return string.Join("\n", depthsList);
        }

        public static void MergeTrees(ProfilerTreeData dest, ProfilerTreeData source)
        {
            MergeTreeNode(dest.Root, source.Root);
        }

        public static ProfilerTreeData SetupTreeFromDepthsList(List<ProfilerTreeNode> depthNodes)
        {
            if (depthNodes == null || depthNodes.Count == 0)
            {
                return null;
            }
            var stackNode = new Stack<ProfilerTreeNode>();
            var root = GetRootTreeNode();
            stackNode.Push(root);
            foreach (var node in depthNodes)
            {
                while (stackNode.Peek().Depth >= node.Depth)
                {
                    stackNode.Pop();
                }
                var curNode = stackNode.Peek();
                curNode.AddChild(node);
                stackNode.Push(node);
            }
            MakeLeaves(root);
            return new ProfilerTreeData(root);
        }

        public static List<List<ProfilerTreeNode>> ConvertTreeToDepthsListBySepNum(ProfilerTreeData profilerTreeData, int sepNum)
        {
            var depthLists = GetNodesDepthListBySepNum(profilerTreeData.Root, sepNum);
            foreach (var depthList in depthLists)
            {
                depthList.RemoveAt(0);  // remove掉默认的根节点
            }
            return depthLists;
        }
        
        public static List<ProfilerTreeNode> ConvertTreeToDepthsList(ProfilerTreeData profilerTreeData)
        {
            var depthList = new List<ProfilerTreeNode>();
            if (profilerTreeData != null)
            {
                GetNodesDepthList(profilerTreeData.Root, ref depthList);
                depthList.RemoveAt(0);  // remove掉默认的根节点
            }
            return depthList;
        }
        
        /// <summary>
        /// 倒序树
        /// </summary>
        /// <param name="profilerTreeData"></param>
        /// <returns></returns>
        public static ProfilerTreeData ReverseTree(ProfilerTreeData profilerTreeData)
        {
            if (profilerTreeData == null)
            {
                return null;
            }
            MakeLeaves(profilerTreeData.Root);

            var rTree = new ProfilerTreeData(GetRootTreeNode());
            var depthNodes = ConvertTreeToDepthsList(profilerTreeData);
            DoubleLinkedList<ProfilerTreeNode> linkedNodes = new DoubleLinkedList<ProfilerTreeNode>();
            foreach (var node in depthNodes)
            {
                while (linkedNodes.TryGetLastValue(out var lastNode))
                {
                    if (lastNode.Depth >= node.Depth)
                    {
                        if (lastNode.IsLeaf)
                        {
                            using (var subTree = SetupReverseTreeFromLinkedNodes(linkedNodes))
                            {
                                MergeTreeNode(rTree.Root, subTree.Root);    
                            }
                        }
                        linkedNodes.RemoveLast();
                    }
                    else
                    {
                        break;
                    }
                }
                
                var revertNode = ProfilerTreeNode.RequestNode(node.Name, node.Depth, node.Gc, node.SelfGc, node.TimeMs,
                    node.SelfMs, node.CallCount, node.IsLeaf);
                linkedNodes.AddLast(revertNode);
                
                if (node.IsLeaf)
                { // 处理下叶子节点是根节点的情况
                    using (var subTree = SetupReverseTreeFromLinkedNodes(linkedNodes))
                    {
                        MergeTreeNode(rTree.Root, subTree.Root);    
                    }
                    linkedNodes.RemoveLast();
                }
            }
            return rTree;
        }
        
        public static ProfilerTreeNode GetRootTreeNode()
        {
            return ProfilerTreeNode.RequestNode("root", -1, 0, 0, 0, 0);
        }
        
        private static void MergeTreeNode(ProfilerTreeNode dest, ProfilerTreeNode source)
        {
            if (dest.Name != source.Name)
            {
                return;
            }
            dest.Gc += source.Gc;
            dest.SelfGc += source.SelfGc;
            dest.TimeMs += source.TimeMs;
            dest.SelfMs += source.SelfMs;
            dest.CallCount += source.CallCount;
            foreach (var srcChild in source.Children)
            {
                bool bMerge = false;
                foreach (var destChild in dest.Children)
                {
                    if (destChild.Name == srcChild.Name)
                    {
                        MergeTreeNode(destChild, srcChild);
                        bMerge = true;
                        break;
                    }
                }
                if (!bMerge)
                {
                    // 需要深拷贝
                    var node = ProfilerTreeNode.DeepCopy(srcChild);
                    dest.AddChild(node);
                }
            }
        }
        
        private static async Task<ProfilerTreeNode> ReverseListAsyncInternal(List<ProfilerTreeNode> depthList)
        {
            var root = GetRootTreeNode();
            DoubleLinkedList<ProfilerTreeNode> linkedNodes = new DoubleLinkedList<ProfilerTreeNode>();
            foreach (var node in depthList)
            {
                while (linkedNodes.TryGetLastValue(out var lastNode))
                {
                    if (lastNode.Depth >= node.Depth)
                    {
                        if (lastNode.IsLeaf)
                        {
                            var subTree = SetupReverseTreeFromLinkedNodes(linkedNodes);
                            MergeTreeNode(root, subTree.Root); 
                        }
                        linkedNodes.RemoveLast();
                    }
                    else
                    {
                        break;
                    }
                }

                linkedNodes.AddLast(node);
                if (node.IsLeaf)
                { // 处理下叶子节点是根节点的情况
                    var subTree = SetupReverseTreeFromLinkedNodes(linkedNodes);
                    MergeTreeNode(root, subTree.Root); 
                    linkedNodes.RemoveLast();
                }
            }
            return root;
        }
        
        /// <summary>
        /// 拆分成多个深度列表
        /// </summary>
        private static List<List<ProfilerTreeNode>> GetNodesDepthListBySepNum(ProfilerTreeNode root, int sepNum)
        {
            var depthLists = new List<List<ProfilerTreeNode>>();
            if (root == null)
            {
                return depthLists;
            }
            // 使用层次遍历（BFS）遍历树，并将节点分配到不同的列表中
            var stack = new Stack<ProfilerTreeNode>();
            stack.Push(root);
            var currentList = new List<ProfilerTreeNode>();
            while (stack.Count > 0)
            {
                var node = stack.Pop();
                currentList.Add(node);
                for (int i = node.Children.Count - 1; i >= 0; i--)
                {
                    stack.Push(node.Children[i]);
                }
                if (currentList.Count >= sepNum && node.IsLeaf && stack.Count > 0)
                {
                    // 拆分到下个列表
                    depthLists.Add(currentList);
                    // 还原下深度列表结构
                    currentList = new List<ProfilerTreeNode>();
                    var parent = node.Parent;
                    while (parent != null)
                    {
                        currentList.Insert(0, parent);
                        parent = parent.Parent;
                    }
                }
            }
            depthLists.Add(currentList);
            return depthLists;
        }
        
        private static void GetNodesDepthList(ProfilerTreeNode root, ref List<ProfilerTreeNode> outDepthList)
        {
            if (root == null)
            {
                return;
            }
            outDepthList.Add(root);
            foreach (var child in root.Children)
            {
                GetNodesDepthList(child, ref outDepthList);
            }
        }
        
        private static ProfilerTreeData SetupReverseTreeFromLinkedNodes(DoubleLinkedList<ProfilerTreeNode> linkedNodes)
        {
            var nodeList = new List<ProfilerTreeNode>(linkedNodes.Count);
            var laskNode = linkedNodes.Last;
            var depth = 0;
            while (laskNode != null)
            {
                var node = (ProfilerTreeNode)laskNode.Value;
                nodeList.Add(ProfilerTreeNode.RequestNode(node.Name, depth, node.Gc, node.SelfGc,  node.TimeMs, node.SelfMs, node.CallCount));
                depth++;
                laskNode = laskNode.Previous;
            }
            return SetupTreeFromDepthsList(nodeList);
        }

        private static void MakeLeaves(ProfilerTreeNode node)
        {
            if (node.Children.Count == 0)
            {
                node.IsLeaf = true;
            }
            else
            {
                node.IsLeaf = false;
                foreach (var child in node.Children)
                {
                    MakeLeaves(child);
                }
            }
        }

        public void Dispose()
        {
            ProfilerTreeNode.ReleaseNode(Root);
        }
    }
}
